//输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 
//
// 示例1： 
//
// 输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4 
//
// 限制： 
//
// 0 <= 链表长度 <= 1000 
//
// 注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/ 
// Related Topics 递归 链表 
// 👍 153 👎 0


package leetcode.editor.cn1;

import com.leetcode.entity.ListNode;

//Java：合并两个排序的链表

/**
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 */
public class HeBingLiangGePaiXuDeLianBiaoLcof {
    public static void main(String[] args) {
        Solution solution = new HeBingLiangGePaiXuDeLianBiaoLcof().new Solution();
        // TO TEST

        ListNode head1 = new ListNode(1);
        ListNode tmp1 = new ListNode(2);
        head1.next = tmp1;
        tmp1.next = new ListNode(4);

        ListNode head2 = new ListNode(1);
        ListNode tmp2 = new ListNode(3);
        head2.next = tmp2;
        tmp2.next = new ListNode(4);

        ListNode res = solution.mergeTwoLists(head1, head2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            // 寻找两个链表第一个节点的较小值
            if (l1 == null && l2 == null)
                return null;
            if (l1 == null)
                return l2;
            if (l2 == null)
                return l1;

            // 不断往链表插入节点
            ListNode resHead = new ListNode(), tmp = null;
            ListNode resTail = resHead;
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    tmp = l1.next;
                    resTail.next = l1;
                    resTail = resTail.next;
                    l1.next = null;
                    l1 = tmp;
                } else if (l1.val > l2.val) {
                    tmp = l2.next;
                    resTail.next = l2;
                    resTail = resTail.next;
                    l2.next = null;
                    l2 = tmp;
                } else {
                    // 接入两次
                    tmp = l1.next;
                    resTail.next = l1;
                    resTail = resTail.next;
                    l1.next = null;
                    l1 = tmp;

                    tmp = l2.next;
                    resTail.next = l2;
                    resTail = resTail.next;
                    l2.next = null;
                    l2 = tmp;
                }
            }

            if (l1 == null && l2 != null) {
                resTail.next = l2;
                resTail = resTail.next;
            }
            if (l2 == null && l1 != null) {
                resTail.next = l1;
                resTail = resTail.next;
            }
            resHead = resHead.next;
            return resHead;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
